#! /usr/bin/python

import math

def isPrime(n):
    if n == 2 or n == 3 or n==5 or n==7: return True
    if n%2 == 0 or n%3==0 or n==1: return False
    i = 5
    while(i<=math.floor(math.sqrt(n))):
         if n%i == 0 or n%(i+2)==0:return False
         i +=6
    return True

print isPrime(25)
upper = 1000000
d = 3
phi=[0]*(upper+1)
phi[2] = 1
primes = [2]

while(d<=upper):
     if isPrime(d):
	phi[d]=d-1
        primes.append(d)
     d +=2

#print len(primes)

for i in primes:
    index = i
    while(index*i <= upper):
	 index *= i	     
	 phi[index] =phi[index/i]*i	 

for i in range(2, upper/3):
    for j in primes:
        index = i*j
	if index > upper: break
	if phi[index] == 0 and i != j:
	   phi[index] = phi[i]*(j-1)
	   while(index*j<=upper):		
		phi[index*j] = phi[index]*j
		index *=j
 		

#print phi.count(0)

#print sum(phi)

print phi[2**6], phi[5**6], phi[upper], phi.count(0), sum(phi)

